home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 3553 < prev    next >
Encoding:
Text File  |  1996-08-05  |  4.0 KB  |  121 lines
  1. Newsgroups: comp.lang.c
  2. Path: munta.cs.mu.OZ.AU!baillie
  3. From: baillie@munta.cs.mu.OZ.AU (Stephen Baillie)
  4. Subject: Re: How to test a random generator ?
  5. Message-ID: <9603010.14743@mulga.cs.mu.OZ.AU>
  6. Sender: news@cs.mu.OZ.AU (CS-Usenet)
  7. Organization: Computer Science, University of Melbourne, Australia
  8. References: <4e2q7g$oe@centre.univ-orleans.fr> <4e933p$t25@longwood.cs.ucf.edu>
  9. Date: Mon, 29 Jan 1996 23:10:50 GMT
  10.  
  11. schnitzi@longwood.cs.ucf.edu (Mark Schnitzius) writes:
  12.  
  13. >emmguyot@desiree.univ-orleans.fr (Emmanuel GUYOT) writes:
  14.  
  15. >>How can I test a random generator ?
  16. >>I need to verify that my random generator is really
  17. >>random. Can you tell me a way to test this ?
  18.  
  19. >Every random number algorithm I've ever seen repeats
  20. >after a given number of digits.  Good ones take a 
  21. >long time to repeat.  See how many digits it takes
  22. >before yours starts to repeat.
  23.  
  24. >If I remember correctly, there's no way to tell if
  25. >a given sequence is truly random.  I think there was
  26. >something about it in The Turing Omnibus by A. K. 
  27. >Dewdney.
  28.  
  29. There are various statistical tests you can use to determine if a
  30. random number generator exhibits certain properties of truly
  31. random sequences.  The most common/appropriate/applicable is
  32. probably the chi squared test.  Basically, you take n random
  33. numbers from the range a - b, then take the sum of the squares
  34. of the differences between the actual occurances of each number
  35. and the expected or average number, take the square root, and
  36. the result should be roughly b-a.  Too close to zero and it's
  37. not random enough; too large and it shows too much bias towards
  38. particular numbers.  An example:
  39.  
  40. #include <stdio.h>
  41. #include <stdlib.h>
  42. #include <math.h>
  43.  
  44. /*
  45.  * chi2.c - a program to apply a chi squared test to a random number
  46.  * generator, to see how "random" it is.
  47.  * Gives the most meaningful values for lots of iterations.
  48.  * Some years ago I stole the basic theory from a textbook, but I've
  49.  * forgotten which one.  This is all off the top of my head.
  50.  * Written by Stephen Baillie, 30/1/96.
  51.  */
  52.  
  53. int main(int argc, char *argv[]);
  54. int main(int argc, char *argv[])
  55. {
  56.     long *counts;
  57.     long range, iterations, i;
  58.     double chi2, average;
  59.  
  60.     if (argc != 3)
  61.     { /* Check parameters and report correct usage */
  62.         printf("Usage: chi2 range iterations\n");
  63.         exit(1);
  64.     }
  65.  
  66.     range = atol(argv[1]);
  67.     iterations = atol(argv[2]);
  68.     if (range < 2)
  69.     { /* Having only one possible result is not random.  < 1 is silly. */
  70.         printf("Error: Range must be at least 2.\n");
  71.         exit(1);
  72.     }
  73.     if (iterations < range)
  74.     { /* Fairly arbitrary cut off value - got a better one? */
  75.         printf("Value of iterations too small for meaningful result.\n");
  76.         exit(1);
  77.     }
  78.     counts = (long *) malloc(range * sizeof(*counts));
  79.     if (counts == NULL)
  80.     { /* Can't continue without space for our results array... */
  81.         printf("Memory allocation failure; wanted %ld bytes.\n",
  82.                 range * sizeof(*counts));
  83.         exit(1);
  84.     }
  85.  
  86.     for (i = 0; i < range; i++)
  87.         counts[i] = 0; /* Start off with no hits. */
  88.  
  89.     for (i = 0; i < iterations; i++)
  90.         counts[random() % range]++; /* Insert your random function here */
  91.  
  92.     /* Calculate the chi squared value, the sum of the squares of the
  93.        deviations from the expected value */
  94.     average = (double) iterations / (double) range;
  95.     for (chi2 = 0, i = 0; i < range; i++)
  96.         chi2 += (counts[i] - average) * (counts[i] - average);
  97.  
  98.     /* Report the chi value, and a very rough assessment of the RNG */
  99.     printf("Chi value = %f ", sqrt(chi2));
  100.     if (sqrt(chi2) < range / 2)
  101.         printf("(not random enough)\n");
  102.     else if (sqrt(chi2) > range * 2)
  103.         printf("(too biased)\n");
  104.     else
  105.         printf("(not bad)\n");
  106.  
  107.     free(counts);
  108.  
  109.     exit(0);
  110. } /* main */
  111.  
  112. Hope this is vaguely useful,
  113.  
  114. Steve.
  115.  
  116. -- 
  117. "If we shadows have offended, Think but this and all is mended:
  118.  That you have but slumbered here, While these visions did appear.
  119.  And this weak and idle theme, no more yielding but a dream."
  120. baillie@munta.cs.mu.oz.au (Stephen Baillie)
  121.